/**
 * 
 * 插入排序（类似打扑克时，抓牌排序）：从左到右，扫描过的是已排序并且换好的，最后一个一定是最大值
 * 
 * 
 * 原创方法：
 * 1.创建一个数组是已排序过的
 * 2.循环原数组，每次插入的时候和最后一位比较，如果小于它则换位，否则不处理
 * 
 * 空间是：O(n)
 * 
 * 思考总结：原创和官方的比较，官方的更好。主要是不会在原数组上操作
 * @param {*} array 
 */
function insertSort2(array){
   let sorted=[];
    for (let i = 0; i < array.length; i++) {
        sorted.push(array[i])
        for (let j = sorted.length-1; j > 0; j--) {
            console.log('c')
            // 如果前面的数大于后面的数，交换位置
            if(sorted[j-1]>sorted[j]){
              const temp=sorted[j];
              sorted[j]=sorted[j-1];
              sorted[j-1]=temp  
              console.log('swap',sorted[j],sorted[j-1])
            }else{
                break;
            }
           
        }
        
        
    }
    return sorted;
}

/**
 * 根据当前的索引，和之前的元素比较，只要之前的元素比它大就交换
 * @param {*} array 
 * @returns 
 */
function insertSort(array){
   
     for (let i = 0; i < array.length; i++) {
        // 
         for (let j = i; j > 0; j--) {
             console.log('c')
             // 如果前面的数大于后面的数，交换位置
             if(array[j-1]>array[j]){
               const temp=array[j];
               array[j]=array[j-1];
               array[j-1]=temp  
               console.log('swap',array[j],array[j-1])
             }else{
                 break;
             }
         } 
     }
     return array;
 }
 console.log(insertSort([21,3,1,5,1]))

/**
 * 数组操作技巧：
 * 1.用一个指针指向排序好最大的值位置，先用一个变量把需要的换位的值保存起来
 * 2.再把对应的值赋值上去
 * @param {*} array 
 * @returns 
 */
function insertSort3(array){
  
    let preIndex=0,current=null;
     for (let i = 0; i < array.length; i++) {
         // 把当前的值先保存起来，等换完之后再插入
         current=array[i]
         preIndex=i-1;
         // 把当前的值和前面的值对比，要是小于就交换位置
        while(preIndex>=0 && array[preIndex] > current) {
             console.log(current,array)
             // 把前面的数换到后面
             array[preIndex+1]=array[preIndex]
             //继续往前指
             preIndex--
            
         }
        
         //等换完之后，因为最后的那个值一定比当前的小，所以直接插入到数组里（覆盖最先没用的值）
          //  如 3 1 2，换完就是 3 3 2，然后1再覆盖3
         array[preIndex+1]=current;
         
         
     }
     return array;
 }
 //console.log(insertSort([5,3,1]))
